package com.example.demo.serive;

import com.alibaba.fastjson.JSON;
import com.example.demo.entity.Box;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
@Service
public class FindPathSevice {

    PriorityQueue<Box> resultList=new PriorityQueue<Box>();
    ArrayList<Box> processList =new ArrayList<Box>();

    public String FindPath(Box [][] boxlist,Box start,Box end) {

        resultList.clear();
        processList.clear();

        //1.把起始格添加到开启列表
        start.seifFactor=start.i;
        start.lengthFactor=getH(start,end);
        start.numsfactor=getnums(start);
        resultList.add(start);
        //2. 重复如下的工作：
        while (!resultList.isEmpty()){
            Box nowbox =resultList.poll();
            processList.add(nowbox);
            if(nowbox.equals(end)){
                end=nowbox;
                break;
            }
            for (Box next : ToLookForPath(boxlist,nowbox)){
                if(processList.contains(next)|| next.i==999){
                    continue;
                }
                if(!resultList.contains(next)){
                    next.father=nowbox;
                    next.lengthFactor=getH(next,end);
                    next.seifFactor=nowbox.seifFactor+next.i;
                    next.numsfactor=getnums(next);
                    resultList.add(next);
                }else{
                    if(next.seifFactor>nowbox.seifFactor+next.i){
                        next.seifFactor=nowbox.seifFactor+next.i;
                        next.father=nowbox;
                        next.numsfactor=getnums(next);
                    }
                }
            }
        }

        if(resultList.isEmpty()){
            System.out.println("没有找到");
        }else{
           return JSON.toJSONString(getpath(end));
        }
        return null;
    }

    public List<Box> getpath(Box end){
        ArrayList<Box> result=new ArrayList<Box>();
//        Box linshi;
        while (end.father!=null){
            result.add(new Box(end.x,end.y));
            end=end.father;
//            linshi=end.father;
//            result.add(end);
//            end=linshi;
        }
        return result;
    }

    public int getH(Box start,Box end){
        return Math.abs(start.x-end.x)+Math.abs(start.y-end.y);
    }
    public int getnums(Box now){
        return now.lengthFactor+now.seifFactor;
    }

    public List<Box> ToLookForPath(Box [][] boxlist,Box nowbox){
        ArrayList<Box> list =new ArrayList<Box>();
        //上
        if(nowbox.x-1>=0){
            list.add(boxlist[nowbox.x-1][nowbox.y]);
        }
        //右上
        if(nowbox.x-1>=0&&nowbox.y+1<boxlist[0].length){
            list.add(boxlist[nowbox.x-1][nowbox.y+1]);
        }
        //右
        if(nowbox.y+1<boxlist[0].length){
            list.add(boxlist[nowbox.x][nowbox.y+1]);
        }
        //右下
        if(nowbox.x+1<boxlist[0].length&&nowbox.y+1<boxlist[0].length){
            list.add(boxlist[nowbox.x+1][nowbox.y+1]);
        }
        //下
        if(nowbox.x+1<boxlist[0].length){
            list.add(boxlist[nowbox.x+1][nowbox.y]);
        }
        //左下
        if(nowbox.x+1<boxlist[0].length&&nowbox.y-1>=0){
            list.add(boxlist[nowbox.x+1][nowbox.y-1]);
        }
        //左
        if(nowbox.y-1>=0){
            list.add(boxlist[nowbox.x][nowbox.y-1]);
        }
        //左上
        if(nowbox.x-1>=0&&nowbox.y-1>=0){
            list.add(boxlist[nowbox.x-1][nowbox.y-1]);
        }
        return list;
    }




}
